<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/astronaut32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/astronaut16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="fonts.googleapis.com/css?family=EB Garamond:300,300italic,400,400italic,700,700italic|Cinzel Decorative:300,300italic,400,400italic,700,700italic|Noto Serif SC:300,300italic,400,400italic,700,700italic|Source Code Pro:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"fat_fat_where_are_you.gitee.io","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"mac"},"back2top":{"enable":false,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

<link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@500&display=swap" rel="stylesheet">
  <meta name="description" content="数据结构与算法概念题">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法概念题">
<meta property="og:url" content="http://fat_fat_where_are_you.gitee.io/archives/608186a4.html">
<meta property="og:site_name" content="肥肉啊肥肉你在哪">
<meta property="og:description" content="数据结构与算法概念题">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-11-20T02:54:52.000Z">
<meta property="article:modified_time" content="2021-11-20T02:54:52.000Z">
<meta property="article:author" content="肥肉啊肥肉你在哪">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="http://fat_fat_where_are_you.gitee.io/archives/608186a4.html">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>
<link rel="stylesheet" type="text/css" href="/css/injector/main.css"><link rel="preload" as="style" href="/css/injector/light.css"><link rel="preload" as="style" href="/css/injector/dark.css">
  <title>数据结构与算法概念题 | 肥肉啊肥肉你在哪</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

  <script src="https://cdn.jsdelivr.net/npm/jquery/dist/jquery.min.js"></script>
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">肥肉啊肥肉你在哪</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-movies">

    <a href="/movies/" rel="section"><i class="fa fa-film fa-fw"></i>观影</a>

  </li>
        <li class="menu-item menu-item-books">

    <a href="/books/" rel="section"><i class="fa fa-book fa-fw"></i>阅读</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" placeholder="搜索..." spellcheck="false" type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="reading-progress-bar"></div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://fat_fat_where_are_you.gitee.io/archives/608186a4.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/touxiang.gif">
      <meta itemprop="name" content="肥肉啊肥肉你在哪">
      <meta itemprop="description" content>
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="肥肉啊肥肉你在哪">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数据结构与算法概念题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-11-20 10:54:52" itemprop="dateCreated datePublished" datetime="2021-11-20T10:54:52+08:00">2021-11-20</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E8%80%83%E7%A0%94/" itemprop="url" rel="index"><span itemprop="name">考研</span></a>
                </span>
            </span>

          
          
          <br>
            <span id="/archives/608186a4.html" class="post-meta-item leancloud_visitors" data-flag-title="数据结构与算法概念题" title="阅读次数">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span class="leancloud-visitors-count"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/archives/608186a4.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/archives/608186a4.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>4.9k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>4 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="数据结构与算法概念题"><a href="# 数据结构与算法概念题" class="headerlink" title="数据结构与算法概念题"></a>数据结构与算法概念题</h1><span id="more"></span>

<ul>
<li><p><strong>线性结构的特点是 </strong>：在数据元素的<strong> 非空有限集 </strong> 中，<br>（1）存在 <strong> 惟一 </strong> 的一个被称作“第一个”的数据元素和 <strong> 惟一 </strong> 的一个被称作“最后一个”的数据元素；<br>（2）除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中的每一个数据元素均只有一个后继。</p>
</li>
<li><p><strong>线性表：</strong>是最常用，最简单的一种数据结构，一个线性表是 n 个数据元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。</p>
</li>
<li><p><strong>顺序存储结构（由此形成顺序表）：</strong>用一组地址连续的存储单元依次存储线性表的数据元素。<strong>优点：</strong>逻辑关系上相邻的两个元素在物理位置上也相邻因此可以随机存取表中任一元素。<strong>缺点：</strong>在插入，删除操作时需移动大量的元素。</p>
</li>
<li><p><strong>链式存储结构（由此形成链表）：</strong>用一组任意的存储单元–结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针)的指针域组成。<strong>优点：</strong>可以大提高存储器的使用效率。</p>
</li>
<li><p><strong>顺序存储结构的特点？</strong></p>
</li>
</ul>
<p>1、结点中只存放数据元素本身的信息，无附加内容。（优点）</p>
<p>2、可直接存储数据元素。（优点）</p>
<p>3、存储操作速度较快。（优点）</p>
<p>4、插入、删除数据元素时，由于需要保持数据元素之间的逻辑关系，必须大量移动元素，因此实现起来比较慢。（缺点）</p>
<p>5、顺序存储是一种静态结构、存储密度大，空间利用率低，预分配空间大小难以确定，（缺点）</p>
<ul>
<li><strong>链式存储结构的特点？</strong></li>
</ul>
<p>1、结点中除存放数据元素本身的信息外，还需存放附加的指针。</p>
<p>2、不能直接存取数据元素，需顺链路查找，存取速度较慢。</p>
<p>3、插入、删除元素时不必移动其他元素，速度较快。（优点）</p>
<p>4、链式存储是一种动态存储结构，空间利用率高，存储密度小，不存在预分配空间问题。</p>
<ul>
<li><p><strong>顺序表：</strong>采用顺序存储结构的线性表通常称为顺序表。</p>
</li>
<li><p><strong>链表：</strong>采用链式存储结构的线性表通常称为顺序表。</p>
</li>
<li><p><strong>线性链表 </strong> 主要有：单链表，双链表，循环链表。</p>
</li>
</ul>
<p>1、<strong>单向链表：</strong>在单链表中，数据元素由数值域和数据元素的指针域两部分组成，即：每一个数据元素 = 数据域 + 直接后继元素的地址。其中终点结点无直接后继，终结点的指针域值为空 NIL。</p>
<p>2、<strong>双向链表：</strong>每一元素的指针域既包含直接后继，也包含直接前趋。即：每一个数据元素 = 直接前驱元素的地址 + 数据域 + 直接后继元素的地址。</p>
<p>3、<strong>循环链表：</strong>是一种首尾连接的链表。表中最后一个节点的指针域指向头节点，整个链表形成一个环。</p>
<ul>
<li><p><strong>栈：</strong>是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底（bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。</p>
</li>
<li><p><strong>栈的顺序存储结构：</strong>利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。</p>
</li>
<li><p>双向栈：使两个栈共享一维数组 stack[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为 -1 和 MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。</p>
</li>
<li><p><strong>栈的链式存储结构：</strong>栈的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储栈中的数据元素，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。</p>
</li>
<li><p><strong>队列：</strong>是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear)，只允许进行删除的一端称为队头（front)。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。因此，队列也被称为“先进先出”表。</p>
</li>
<li><p><strong>队列的顺序存储结构：</strong>利用一组地址连续的存储单元依次存放队列中的数据元素，称为队列的顺序存储结构。</p>
</li>
<li><p><strong>队列的链式存储结构：</strong>队列的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储队列中的数据元素，这种结构的队列称为链队列。在一个链队列中需设定两个指针（头指针和尾指针）分别指向队列的头和尾。</p>
</li>
<li><p><strong>非线性结构的逻辑特征</strong>：一个结点元素可能有多个直接前趋和多个直接后趋。</p>
</li>
<li><p><strong>树：</strong>是 n 个结点的有限集合，n≥0，有且只有一个称为根的结点，根结点无前驱</p>
</li>
<li><p><strong>二叉树：</strong>有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。</p>
</li>
<li><p><strong>满二又树：</strong>深度为 k 且有 2k-1 个结点的二又树称为满二又树。</p>
</li>
<li><p><strong>完全二叉树：</strong>深度为 k 的，有 n 个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二又树中编号从 1 至 n 的结点一一对应称为完全二叉树。</p>
</li>
<li><p><strong>线索二叉树：</strong>若结点 p 有左孩子，则 p-&gt;1child 指向其左孩子结点，否则令其指向其（中序）前驱。若结点 p 有右孩子，则 p-&gt;rchild 指向其右孩子结点，否则令其指向其（中序)后继。</p>
</li>
<li><p><strong>哈夫曼树：</strong>又称最优二叉树，是一类带权路径长度最短的树．</p>
</li>
<li><p><strong>哈夫曼编码：</strong>在哈夫曼树中，约定左分支代表 0，右分支代表 1，把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来，组成的字符串称为该叶子结点的哈夫曼编码，这就是哈夫曼编码</p>
</li>
<li><p><strong>堆：</strong>如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（如果有的话)的元素，则称此完全二叉树为最大堆。</p>
</li>
</ul>
<p>​       同样，如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最小堆。</p>
<ul>
<li><strong>二叉排序树：</strong>二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：</li>
</ul>
<p>​    1、若它的左子树非空，则左子树上的所有结点的值均小于它的根结点的值。</p>
<p>​    2、若它的右子树非空，则右子树上的所有结点的值均大于或等于它的根结点的值。</p>
<p>​    3、它的左右子树分别为二又排序树。</p>
<ul>
<li><strong>平衡二叉树：</strong>平衡二叉树又称 avl 树，是一种特殊的二叉排序树。AVL 树或者是一颗空二叉树，或者具有如下性质的二又查找树：</li>
</ul>
<p>​    其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过 1。</p>
<ul>
<li><p><strong>图：</strong>一个图 G=（V，E)是一个由非空的有限集 V 和一个边集 E 所组成的。若 E 中的每条边都是顶点的有序对（v，w），就说该图是 <strong> 有向图 </strong>（directed graph，digraph)。若 E 中的每条边是两个不同顶点无序对，就说该图是<strong> 无向图</strong>，其边仍表示成（v，w）。</p>
</li>
<li><p><strong>最小生成树：</strong>设 G=（V，E）是一个连通图，E 中每一条边（u，v)的权为 C（u，v)，也叫做边长。图 G 的一株生成树（spanning tree)是连接 V 中所有结点的一株开放树。将生成树中所有边长之总和称为生成树的价（cost)。使这个价最小的生成树称为图 G 的最小生成树。</p>
</li>
<li><p><strong>邻接矩阵：</strong>表示图中结点之间关系的矩阵称为邻接矩阵</p>
</li>
<li><p><strong>邻接表：</strong>由顶点数据表和表示数据关系的边（弧）构成的表</p>
</li>
<li><p><strong>邻接矩阵表示法的特点？</strong></p>
</li>
</ul>
<p>1．对于无向图而言，它的邻接矩阵是对称矩阵，因此可以采用特殊矩阵的压缩存储法，但对于有向图而言，其中的弧是有方向的，因此有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的存储则需要 n*n 个存储空间．</p>
<p>2．采用邻接矩阵表示法，便于判断图中任意两个顶点之间是否有边相连，即根据邻接矩阵中的信息来判断，另外还便于求得各个顶点的度，对于无向图而言，其邻接矩阵第 i 行元素之和就是图中第 i 个顶点的度</p>
<ul>
<li><strong>邻接表表示法的特点？</strong></li>
</ul>
<p>1．n 个顶点，e 条边的无向图，若采取邻接表作为存储结构，需要 n 个顶点数据和 2e 个表示边的结点，显然在边很稀疏的情况下，用邻接表存储所需的空间比邻接矩阵所需的空间少</p>
<p>2．无向图的度，在无向图的邻接表中，顶点 Vi 的度恰好就是第 i 个边链表上结点的</p>
<p>3．有向图的度，在有向图中，第 i 个边链表上结点的个数就是顶点 Vi 的出度，只需通过表头向量表中找到第 i 个顶点的边链表的头指针，实现顺链查找计数即可</p>
<h1 id="算法概念题"><a href="# 算法概念题" class="headerlink" title="算法概念题"></a>算法概念题</h1><ul>
<li><strong>分治策略：</strong>对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。</li>
<li><strong>步骤：</strong>分治法在每一层递归上都有三个步骤： </li>
</ul>
<p>（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。 </p>
<p>（2）求解：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。 </p>
<p>（3）合并：将各个子问题的解合并为原问题的解。</p>
<ul>
<li><strong>基本要素：</strong>分治法所能解决的问题一般具有以下几个特征：</li>
</ul>
<ol>
<li><ol>
<li>该问题的规模缩小到一定的程度就可以容易地解决；</li>
<li>该问题可以分解为若干个规模较小的相同问题，即该问题具有 <strong> 最优子结构性质</strong>。</li>
</ol>
</li>
<li><ol>
<li>利用该问题分解出的子问题的解可以合并为该问题的解；</li>
<li>该问题所分解出的各个子问题是 <strong> 相互独立 </strong> 的，即子问题之间不包含公共的子子问题。</li>
</ol>
</li>
</ol>
<p>上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好</p>
<ul>
<li><strong>动态规划：</strong>基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。</li>
<li><strong>步骤：</strong></li>
</ul>
<p>（1）分析最优解结构 </p>
<p>（2）建立递推关系</p>
<p>（3）计算最优值</p>
<p>（4）构造最优解</p>
<ul>
<li><strong>基本要素：</strong>能采用动态规划求解的问题的一般要具有 3 个性质：</li>
</ul>
<p>(1) <strong>最优化原理：</strong>如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。</p>
<p>(2) <strong>无后效性</strong>：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。</p>
<p>(3) <strong>有重叠子问题：</strong>即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）</p>
<ul>
<li><strong>动态规划算法与分治算法：</strong></li>
</ul>
<p>相同点：<br>1，两者都是将大问题分解成若干个小问题，<br>2，两者都是依赖于小问题的解决，来解决上一级较大问题</p>
<p>不同点：<br>1，分治法往往用到递归计算，自上而下计算，而动态规划则直接自底向上计算<br>2，分治大的小问题在递归的过程中可能会被反复计算，动态规划中的小问题计算后被存储，下次再碰到时直接调用、<br>3，分治法的小问题的解只使用一次，动态规划的小问题的解存储以备大问题求解时反复调用</p>
<ul>
<li><strong>贪心算法：</strong>顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。</li>
<li><strong>贪心算法的基本要素：</strong></li>
</ul>
<p>1.<strong>贪心选择性质：</strong>所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。</p>
<p>2.<strong>最优子结构：</strong> 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。</p>
<ul>
<li><strong>贪心算法与动态规划：</strong></li>
</ul>
<p>动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。</p>

    </div>

    
    
    
      
  <div class="popular-posts-header">相关文章推荐</div>
  <ul class="popular-posts">
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\archives\9ced5463.html" rel="bookmark">考研数据结构代码整理</a></div>
    </li>
  </ul>

        <div class="reward-container">
  <div>感谢各位打赏的小伙伴</div>
  <button onclick="var qr = document.getElementById('qr'); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
      
      <div style="display: inline-block;">
        <img src="/images/wechatpay.png" alt="肥肉啊肥肉你在哪 微信支付">
        <p>微信支付</p>
      </div>
      
      <div style="display: inline-block;">
        <img src="/images/alipay.png" alt="肥肉啊肥肉你在哪 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>肥肉啊肥肉你在哪
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://fat_fat_where_are_you.gitee.io/archives/608186a4.html" title="数据结构与算法概念题">http://fat_fat_where_are_you.gitee.io/archives/608186a4.html</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow noopener noreferrer" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"><i class="fas fa-tags"></i> 数据结构</a>
          </div>

        
  <div class="post-widgets">
    <div class="wp_rating">
      <div id="wpac-rating"></div>
    </div>
  </div>


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/archives/13675369.html" rel="prev" title="C 语言学习笔记（下）">
      <i class="fa fa-chevron-left"></i> C 语言学习笔记（下）
    </a></div>
      <div class="post-nav-item">
    <a href="/archives/ec1824d4.html" rel="next" title="IT 行业三大定律">
      IT 行业三大定律 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E6%A6%82%E5%BF%B5%E9%A2%98"><span class="nav-text">数据结构与算法概念题</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E6%A6%82%E5%BF%B5%E9%A2%98"><span class="nav-text">算法概念题</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="肥肉啊肥肉你在哪" src="/images/touxiang.gif">
  <p class="site-author-name" itemprop="name">肥肉啊肥肉你在哪</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">38</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">16</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/feirouafeirou" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;feirouafeirou" rel="external nofollow noopener noreferrer" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://wpa.qq.com/msgrd?v=3&uin=1729013657&site=qq&menu=yes" title="QQ → http:&#x2F;&#x2F;wpa.qq.com&#x2F;msgrd?v&#x3D;3&amp;uin&#x3D;1729013657&amp;site&#x3D;qq&amp;menu&#x3D;yes" rel="external nofollow noopener noreferrer" target="_blank"><i class="fab fa-qq fa-fw"></i>QQ</a>
      </span>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="http://www.woshipm.com/" title="http:&#x2F;&#x2F;www.woshipm.com" rel="external nofollow noopener noreferrer" target="_blank">人人都是产品经理</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="http://www.chanpin100.com/" title="http:&#x2F;&#x2F;www.chanpin100.com" rel="external nofollow noopener noreferrer" target="_blank">产品壹佰</a>
        </li>
    </ul>
  </div>

      </div>

    </div>
  </aside>

  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2020 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">肥肉啊肥肉你在哪</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-area"></i>
    </span>
    <span title="站点总字数">237k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">3:35</span>
</div>

<div class="translate-style">
繁/简：<a id="translateLink" href="javascript:translatePage();">繁体
</a>
</div>
<script type="text/javascript" src="/js/tw_cn.js"></script>
<script type="text/javascript">
var defaultEncoding = 2; //网站编写字体是否繁体，1-繁体，2-简体
var translateDelay = 0; //延迟时间,若不在前, 要设定延迟翻译时间, 如100表示100ms,默认为0
var cookieDomain = "https://feirouafeirou.github.io/"; //Cookie地址, 一定要设定, 通常为你的网址
var msgToTraditionalChinese = "繁体"; //此处可以更改为你想要显示的文字
var msgToSimplifiedChinese = "简体"; //同上，但两处均不建议更改
var translateButtonId = "translateLink"; //默认互换id
translateInitilization();
</script>


        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/lozad@1/dist/lozad.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>


  <script defer src="/lib/three/three.min.js"></script>


  



  <script>
  if (CONFIG.page.isPost) {
    wpac_init = window.wpac_init || [];
    wpac_init.push({
      widget: 'Rating',
      id    : 26171,
      el    : 'wpac-rating',
      color : 'fc6423'
    });
    (function() {
      if ('WIDGETPACK_LOADED' in window) return;
      WIDGETPACK_LOADED = true;
      var mc = document.createElement('script');
      mc.type = 'text/javascript';
      mc.async = true;
      mc.src = '//embed.widgetpack.com/widget.js';
      var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(mc, s.nextSibling);
    })();
  }
  </script>

  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : false,
      appId      : 'puzQn5yHhkbtBj2VGFbqJ4FE-MdYXbMMI',
      appKey     : 'lmcgKM2surcxNxMRiqInHjkU',
      placeholder: "Just go go",
      avatar     : 'retro',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : true,
      lang       : '' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>
<div class="moon-menu">
  <div class="moon-menu-items">
    
    <div id="moon-menu-item-back2bottom" class="moon-menu-item" onclick="back2bottom()">
      <i class="fa fa-chevron-down"></i>    </div>
    
    <div id="moon-menu-item-back2top" class="moon-menu-item" onclick="back2top()">
      <i class="fa fa-chevron-up"></i>    </div>
    
  </div>
  <div class="moon-menu-button">
    <svg class="moon-menu-bg">
      <circle class="moon-menu-cricle" cx="50%" cy="50%" r="44%"/>
      <circle class="moon-menu-border" cx="50%" cy="50%" r="48%"/>
    </svg>
    <div class="moon-menu-content">
      <div class="moon-menu-icon"><i class="fas fa-ellipsis-v"></i></div>
      <div class="moon-menu-text"></div>
    </div>
  </div>
</div><script src="/js/injector.js"></script>
<!-- 数字雨 -->
<!-- <canvas id="canvas" width="1440" height="900" ></canvas> -->
<!-- <script type="text/javascript" src="/js/src/DigitalRain.js"></script> -->
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>
<!--浏览器搞笑标题-->
<script type="text/javascript" src="/js/FunnyTitle.js"></script>
<!-- Live2D看板娘 -->
<!-- <script src="/live2d-widget/autoload.js"></script> -->
<!-- <script src="https://feirouafeirou.github.io/live2d-widget/autoload.js"></script> -->
<!-- 网页音乐播放器 -->
<!-- <link rel="stylesheet" href="/dist/APlayer.min.css">
<div id="aplayer"></div>
<script type="text/javascript" src="/dist/APlayer.min.js"></script>
<script type="text/javascript" src="/dist/music.js"></script> -->
</body>

</html>
